5198. Возведение в степень
Вычислите значение выражения xn mod m.
Вход. Три
натуральных числа x, n, m
(1 ≤ x, n ≤ 109, 2 ≤ m ≤ 109).
Выход. Выведите
одно число, равное xn mod m.
|
Пример
входа |
Пример
выхода |
|
2 3 100 |
8 |
РЕШЕНИЕ
рекурсия
Анализ алгоритма
Для возведения в
степень xn mod m воспользуемся формулой:
xn mod m =
Реализация алгоритма
Функция powmod вычисляет значение xn mod m.
long long
powmod(long long x, long long n, long long m)
{
if (n
== 0) return 1;
if (n %
2 == 0) return powmod((x * x) % m, n / 2, m);
return (x *
powmod(x, n - 1, m)) % m;
}
Основная часть программы. Читаем
входные данные.
scanf("%lld %lld %lld",
&x, &n, &m);
Вычисляем значение xn mod m.
res = powmod(x, n, m);
Выводим ответ.
printf("%lld\n",
res);
Java реализация
import java.util.*;
public class Main
{
static long PowMod(long x, long n, long m)
{
if (n == 0) return 1;
if (n % 2 == 0) return PowMod((x * x) % m, n / 2, m);
return (x * PowMod(x, n - 1, m)) % m;
}
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
long x = con.nextLong();
long n = con.nextLong();
long m = con.nextLong();
long res = PowMod(x, n, m);
System.out.println(res);
con.close();
}
}
Java реализация – BigInteger
import java.util.*;
import java.math.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new
Scanner(System.in);
BigInteger a = con.nextBigInteger();
BigInteger b = con.nextBigInteger();
BigInteger m = con.nextBigInteger();
System.out.println(a.modPow(b, m));
con.close();
}
}
Python реализация – pow
Читаем входные
данные.
x, n, m = map(int, input().split())
Вычисляем и выводим ответ.
print(pow(x, n, m))
Python реализация –
рекурсия
Функция myPow вычисляет значение xn mod m.
def myPow(x, n, m):
if (n == 0): return 1
if (n % 2 == 0): return myPow((x * x) % m, n / 2, m)
return (x * myPow(x, n - 1, m)) % m
Основная часть программы. Читаем входные данные.
x, n, m = map(int, input().split())
Вычисляем и выводим ответ.
print(myPow(x, n, m))